Module (scheme lazy)
Delayed evaluation
[syntax] (delay <expression>)Semantics: The delay construct is used together with the procedure force to implement lazy evaluation or call by need. (delay <expression>) returns an object called a promise which at some point in the future can be asked (by the force procedure) to evaluate <expression>, and deliver the resulting value. The effect of <expression> returning multiple values is unspecified.
[syntax] (delay-force <expression>)Semantics: The expression (delay-force expression) is conceptually similar to (delay (force expression)), with the difference that forcing the result of delay-force will in effect result in a tail call to (force expression), while forcing the result of (delay (force expression)) might not. Thus iterative lazy algorithms that might result in a long series of chains of delay and force can be rewritten using delay-force to prevent consuming unbounded space during evaluation.
[syntax] (force promise)The force procedure forces the value of a promise created by delay, delay-force, or make-promise.If no value has been computed for the promise, then a value is computed and returned. The value of the promise must be cached (or "memoized") so that if it is forced a second time, the previously computed value is returned. Consequently, a delayed expression is evaluated using the parameter values and exception handler of the call to force which first requested its value. If promise is not a promise, it may be returned unchanged.
(force (delay (+ 1 2))) ==> 3
(let ((p (delay (+ 1 2))))
(list (force p) (force p))) ==> (3 3)
(define integers
(letrec ((next
(lambda (n)
(delay (cons n (next (+ n 1)))))))
(next 0)))
(define head
(lambda (stream) (car (force stream))))
(define tail
(lambda (stream) (cdr (force stream))))
(head (tail (tail integers))) ==> 2
The following example is a mechanical transformation of a lazy stream-filtering algorithm into Scheme. Each call to a constructor is wrapped in delay, and each argument passed to a deconstructor is wrapped in force. The use of (delay-force ...) instead of (delay (force ...)) around the body of the procedure ensures that an ever-growing sequence of pending promises does not exhaust available storage, because force will in effect force such sequences iteratively.
(define (stream-filter p? s)
(delay-force
(if (null? (force s))
(delay '())
(let ((h (car (force s)))
(t (cdr (force s))))
(if (p? h)
(delay (cons h (stream-filter p? t)))
(stream-filter p? t))))))
(head (tail (tail (stream-filter odd? integers)))) ==> 5
The following examples are not intended to illustrate good programming style, as delay, force, and delay-force are mainly intended for programs written in the functional style. However, they do illustrate the property that only one value is computed for a promise, no matter how many times it is forced.
(define count 0)
(define p
(delay (begin (set! count (+ count 1))
(if (> count x)
count
(force p)))))
(define x 5)
p ==> a promise
(force p) ==> 6
p ==> a promise, still
(begin (set! x 10)
(force p)) ==> 6
Various extensions to this semantics of delay, force and delay-force are supported in some implementations:
- Calling force on an object that is not a promise may simply return the object.
- It may be the case that there is no means by which a promise can be operationally distinguished from its forced value. That is, expressions like the following may evaluate to either #t or to #f, depending on the implementation:
(eqv? (delay 1) 1) ==> unspecified (pair? (delay (cons 1 2))) ==> unspecified
- Implementations may implement “implicit forcing,” where the value of a promise is forced by procedures that operate only on arguments of a certain type, like cdr and *. However, procedures that operate uniformly on their arguments, like list, must not force them.
(+ (delay (* 3 7)) 13) ==> unspecified (car (list (delay (* 3 7)) 13)) ==> a promise[procedure] (promise? obj)
The promise? procedure returns #t if its argument is a promise, and #f otherwise. Note that promises are not necessarily disjoint from other Scheme types such as procedures.
<procedure>(make-promise obj)</promise>
The make-promise procedure returns a promise which, when forced, will return obj. It is similar to delay, but does not delay its argument: it is a procedure rather than syntax. If obj is already a promise, it is returned.
Previous: Module (scheme inexact)
Next: Module (scheme load)